package lc.q51_100;

/**
 * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
 */
public class Q61 {

    public static class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
    }

    public ListNode rotateRight(ListNode head, int k) {
        // 弄个指针，向右移动n个节点
        // 先计算长度
        int n = 0;
        ListNode tail = head;
        while (tail != null) {
            n ++;
            tail = tail.next;
        }
        if (n <= 1) {
            return head;
        }
        // 重算k
        k = k % n;
        if (k == 0) {
            return head;
        }
        int j = 0;
        tail = head;
        ListNode newHead = head;
        ListNode preHead = null;
        while (tail.next != null) {
            tail = tail.next;
            j ++;
            if (j >= k) {
                preHead = newHead;
                newHead = newHead.next;
            }
        }
        tail.next = head;
        if (preHead != null) {
            preHead.next = null;
        }
        return newHead;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2};
        ListNode pre = new ListNode(0);
        ListNode next = pre;
        for (int i = 0; i < nums.length; i++) {
            next.next = new ListNode(nums[i]);
            next = next.next;
        }
        ListNode listNode = new Q61().rotateRight(pre.next, 1);
        while (listNode != null) {
            System.out.print(listNode.val +"\t");
            listNode = listNode.next;
        }
    }

}
